package com.datastructure.test.finderrorinsearchtree;

import java.util.*;

public class FindErrorInSearchTree {

    List<Integer> list = new ArrayList();
    public int[] findError (TreeNode root) {
        //结果数组
        int[] result = new int[2];
        //特别判断
        if(root == null) {
            return result;
        }
        //函数调用：从根节点开始查找
        findErrorHelper(root);
        //声明两个循环外的全局变量，用于循环
        int i, j;
        for(i = 0; i < list.size() - 1; i++) {
            //如果满足条件,更新结果集
            if(list.get(i) > list.get(i + 1)){
                result[1] = list.get(i);
                break;
            }
        }
        for(j = list.size() - 1; j > i; j--) {
            //如果满足条件，同样更新结果集
            if(list.get(j) < list.get(j - 1)) {
                result[0] = list.get(j);
                //结束循环
                break;
            }
        }
        //返回结果
        return result;
    }

    //递归求解
    private void findErrorHelper(TreeNode root) {
        //特判
        if(root != null) {
            //中序遍历：对左孩纸进行递归
            findErrorHelper(root.left);
            //将根节点添加到list中
            list.add(root.val);
            //对右孩纸进行递归
            findErrorHelper(root.right);
        }
    }
}
class TreeNode {
   int val = 0;

    public TreeNode(int val) {
        this.val = val;
    }

    TreeNode left = null;
   TreeNode right = null;
}
